package 递归回溯.二维版;

import javafx.util.Pair;

import java.util.ArrayDeque;
import java.util.Deque;

public class No200岛屿数量 {

    /**
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     *
     * 示例 1：
     * 输入：grid = [
     *   ["1","1","1","1","0"],
     *   ["1","1","0","1","0"],
     *   ["1","1","0","0","0"],
     *   ["0","0","0","0","0"]
     * ]
     * 输出：1
     * 示例 2：
     * 输入：grid = [
     *   ["1","1","0","0","0"],
     *   ["1","1","0","0","0"],
     *   ["0","0","1","0","0"],
     *   ["0","0","0","1","1"]
     * ]
     * 输出：3
     */

    private char[][] arr;
    private boolean[][] flag;
    private int allLength;
    private int itemLength;
    //上 右 下 左
    private int[][] around={{-1,0},{0,1},{1,0},{0,-1}};

    //此乃深度优先
    public int numIslands(char[][] grid) {
        this.allLength=grid.length;
        this.itemLength=grid[0].length;
        this.flag=new boolean[allLength][itemLength];
        this.arr=grid;
        int count=0;
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if(!(arr[i][j]=='0'||flag[i][j])) {
                    dg(i,j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dg(int startX,int startY){

        /**
         * 分析各种情况:
         * 1.是水地,就直接返回false
         * 2.是陆地,可以让它继续走,继续遍历上下左右
         * 3.是足迹,就直接返回false
         */
        if(arr[startX][startY]=='0'||flag[startX][startY])
            return;//是水或者足迹就停止

        //标记足迹,无需取消
        flag[startX][startY]=true;
        //是陆地,开始遍历上下左右
        for (int i = 0; i < 4; i++) {
            int newX=startX+around[i][0];
            int newY=startY+around[i][1];
            //不越边界&&是陆地&&未有足迹
            if(newX>=0&&newX<=allLength-1&&newY>=0&&newY<=itemLength-1&&arr[newX][newY]=='1'&&!flag[newX][newY]) {
                //无需打理结果
                dg(newX, newY);
            }
        }
    }

    /**
     * 深度和广度的区别是:
     * 深度:上右下左遇到了就立即冲到底
     * 广度:当前节点上右下左探索(只会探索一个)完之后,再探索下一个节点
     */

    //再来试一试广度优先遍历
    public int numIslands2(char[][] grid){
        this.arr=grid;
        this.allLength=grid.length;
        this.itemLength=grid[0].length;
        flag=new boolean[allLength][itemLength];
        Deque<Pair<Integer,Integer>> queue=new ArrayDeque<>();
        int count=0;
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                //未有足迹&&为陆地
                if(!flag[i][j]&&arr[i][j]=='1'){
                    dg2(i,j,queue);
                    count++;
                }
            }
        }
        return count;
    }

    private void dg2(int startX,int startY,Deque<Pair<Integer,Integer>> queue){

        flag[startX][startY]=true;

        //放入当前岛的坐标
        queue.addLast(new Pair<>(startX,startY));

        while (!queue.isEmpty()){
            Pair<Integer, Integer> pair = queue.removeFirst();
            for (int i = 0; i < 4; i++) {
                int newX = pair.getKey() + around[i][0];
                int newY = pair.getValue() + around[i][1];
                if (newX >= 0 && newX <= allLength - 1 && newY >= 0 && newY <= itemLength - 1
                        && arr[newX][newY] == '1' && !flag[newX][newY]) {
                    flag[newX][newY] = true;
                    queue.addLast(new Pair<>(newX, newY));
                }
            }
        }
    }

    public static void main(String[] args) {
        No200岛屿数量 n=new No200岛屿数量();
        int i = n.numIslands2(new char[][]{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        });
        System.out.println(i);
    }

}
